<html>
  <head>
  <title>mazeGenerator.py</title>
  </head>
  <body>
  <h3>mazeGenerator.py (<a href="../mazeGenerator.py">original</a>)</h3>
  <hr>
  <pre>
<span style="color: green; font-style: italic"># mazeGenerator.py
# ----------------
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html

</span><span style="color: blue; font-weight: bold">import </span>random

<span style="color: darkred">"""
maze generator code

algorithm:
start with an empty grid
draw a wall with gaps, dividing the grid in 2
repeat recursively for each sub-grid

pacman details:
players 1,3 always start in the bottom left; 2,4 in the top right
food is placed in dead ends and then randomly (though not too close to the pacmen starting positions)

notes:
the final map includes a symmetric, flipped copy
the first wall has k gaps, the next wall has k/2 gaps, etc. (min=1)

@author: Dan Gillick
"""

</span>W <span style="font-weight: bold">= </span><span style="color: red">'%'
</span>F <span style="font-weight: bold">= </span><span style="color: red">'.'
</span>C <span style="font-weight: bold">= </span><span style="color: red">'o'
</span>E <span style="font-weight: bold">= </span><span style="color: red">' '

</span><span style="color: blue; font-weight: bold">class </span>Maze<span style="font-weight: bold">:

    </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>rows<span style="font-weight: bold">, </span>cols<span style="font-weight: bold">, </span>anchor<span style="font-weight: bold">=(</span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">), </span>root<span style="font-weight: bold">=</span><span style="color: blue">None</span><span style="font-weight: bold">):
        </span><span style="color: darkred">"""
        generate an empty maze
        anchor is the top left corner of this grid's position in its parent grid
        """
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r <span style="font-weight: bold">= </span>rows
        <span style="color: blue">self</span><span style="font-weight: bold">.</span>c <span style="font-weight: bold">= </span>cols
        <span style="color: blue">self</span><span style="font-weight: bold">.</span>grid <span style="font-weight: bold">= [[</span>E <span style="color: blue; font-weight: bold">for </span>col <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>cols<span style="font-weight: bold">)] </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>rows<span style="font-weight: bold">)]
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>anchor <span style="font-weight: bold">= </span>anchor
        <span style="color: blue">self</span><span style="font-weight: bold">.</span>rooms <span style="font-weight: bold">= []
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root <span style="font-weight: bold">= </span>root
        <span style="color: blue; font-weight: bold">if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">: </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root <span style="font-weight: bold">= </span><span style="color: blue">self

    </span><span style="color: blue; font-weight: bold">def </span>to_map<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
        </span><span style="color: darkred">"""
        add a flipped symmetric copy on the right
        add a border
        """

        </span><span style="color: green; font-style: italic">## add a flipped symmetric copy
        </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r<span style="font-weight: bold">):
            </span><span style="color: blue; font-weight: bold">for </span>col <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">, -</span><span style="color: red">1</span><span style="font-weight: bold">, -</span><span style="color: red">1</span><span style="font-weight: bold">):
                </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span>row<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">].</span>append<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">])
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c <span style="font-weight: bold">*= </span><span style="color: red">2

        </span><span style="color: green; font-style: italic">## add a border
        </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r<span style="font-weight: bold">):
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">] = [</span>W<span style="font-weight: bold">] + </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">] + [</span>W<span style="font-weight: bold">]
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c <span style="font-weight: bold">+= </span><span style="color: red">2
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>insert<span style="font-weight: bold">(</span><span style="color: red">0</span><span style="font-weight: bold">, [</span>W <span style="color: blue; font-weight: bold">for </span>c <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c<span style="font-weight: bold">)])
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>append<span style="font-weight: bold">([</span>W <span style="color: blue; font-weight: bold">for </span>c <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c<span style="font-weight: bold">)])
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r <span style="font-weight: bold">+= </span><span style="color: red">2

    </span><span style="color: blue; font-weight: bold">def </span>__str__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
        </span>s <span style="font-weight: bold">= </span><span style="color: red">''
        </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r<span style="font-weight: bold">):
            </span><span style="color: blue; font-weight: bold">for </span>col <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c<span style="font-weight: bold">):
                </span>s <span style="font-weight: bold">+= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">]
            </span>s <span style="font-weight: bold">+= </span><span style="color: red">'\n'
        </span><span style="color: blue; font-weight: bold">return </span>s<span style="font-weight: bold">[:-</span><span style="color: red">1</span><span style="font-weight: bold">]

    </span><span style="color: blue; font-weight: bold">def </span>add_wall<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>i<span style="font-weight: bold">, </span>gaps<span style="font-weight: bold">=</span><span style="color: red">1</span><span style="font-weight: bold">, </span>vert<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">):
        </span><span style="color: darkred">"""
        add a wall with gaps
        """
        </span>add_r<span style="font-weight: bold">, </span>add_c <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>anchor
        <span style="color: blue; font-weight: bold">if </span>vert<span style="font-weight: bold">:
            </span>gaps <span style="font-weight: bold">= </span>min<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r<span style="font-weight: bold">, </span>gaps<span style="font-weight: bold">)
            </span>slots <span style="font-weight: bold">= [</span>add_r<span style="font-weight: bold">+</span>x <span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r<span style="font-weight: bold">)]
            </span><span style="color: blue; font-weight: bold">if not </span><span style="color: red">0 </span><span style="color: blue; font-weight: bold">in </span>slots<span style="font-weight: bold">:
                </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>min<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">)-</span><span style="color: red">1</span><span style="font-weight: bold">][</span>add_c<span style="font-weight: bold">+</span>i<span style="font-weight: bold">] == </span>E<span style="font-weight: bold">: </span>slots<span style="font-weight: bold">.</span>remove<span style="font-weight: bold">(</span>min<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">))
                </span><span style="color: blue; font-weight: bold">if </span>len<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">) &lt;= </span>gaps<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">0 
            </span><span style="color: blue; font-weight: bold">if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">.</span>c<span style="font-weight: bold">-</span><span style="color: red">1 </span><span style="color: blue; font-weight: bold">in </span>slots<span style="font-weight: bold">:
                </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>max<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">)+</span><span style="color: red">1</span><span style="font-weight: bold">][</span>add_c<span style="font-weight: bold">+</span>i<span style="font-weight: bold">] == </span>E<span style="font-weight: bold">: </span>slots<span style="font-weight: bold">.</span>remove<span style="font-weight: bold">(</span>max<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">))
            </span><span style="color: blue; font-weight: bold">if </span>len<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">) &lt;= </span>gaps<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">0
            </span>random<span style="font-weight: bold">.</span>shuffle<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">)
            </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>slots<span style="font-weight: bold">[</span>gaps<span style="font-weight: bold">:]:
                </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>add_c<span style="font-weight: bold">+</span>i<span style="font-weight: bold">] = </span>W
            <span style="color: blue">self</span><span style="font-weight: bold">.</span>rooms<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>Maze<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r<span style="font-weight: bold">, </span>i<span style="font-weight: bold">, (</span>add_r<span style="font-weight: bold">,</span>add_c<span style="font-weight: bold">), </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">))
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rooms<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>Maze<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c<span style="font-weight: bold">-</span>i<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">, (</span>add_r<span style="font-weight: bold">,</span>add_c<span style="font-weight: bold">+</span>i<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">), </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">))
        </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
            </span>gaps <span style="font-weight: bold">= </span>min<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c<span style="font-weight: bold">, </span>gaps<span style="font-weight: bold">)
            </span>slots <span style="font-weight: bold">= [</span>add_c<span style="font-weight: bold">+</span>x <span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c<span style="font-weight: bold">)]
            </span><span style="color: blue; font-weight: bold">if not </span><span style="color: red">0 </span><span style="color: blue; font-weight: bold">in </span>slots<span style="font-weight: bold">:
                </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>add_r<span style="font-weight: bold">+</span>i<span style="font-weight: bold">][</span>min<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">)-</span><span style="color: red">1</span><span style="font-weight: bold">] == </span>E<span style="font-weight: bold">: </span>slots<span style="font-weight: bold">.</span>remove<span style="font-weight: bold">(</span>min<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">))
                </span><span style="color: blue; font-weight: bold">if </span>len<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">) &lt;= </span>gaps<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">0
            </span><span style="color: blue; font-weight: bold">if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span><span style="color: red">1 </span><span style="color: blue; font-weight: bold">in </span>slots<span style="font-weight: bold">:
                </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>add_r<span style="font-weight: bold">+</span>i<span style="font-weight: bold">][</span>max<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">)+</span><span style="color: red">1</span><span style="font-weight: bold">] == </span>E<span style="font-weight: bold">: </span>slots<span style="font-weight: bold">.</span>remove<span style="font-weight: bold">(</span>max<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">))
            </span><span style="color: blue; font-weight: bold">if </span>len<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">) &lt;= </span>gaps<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">0
            </span>random<span style="font-weight: bold">.</span>shuffle<span style="font-weight: bold">(</span>slots<span style="font-weight: bold">)
            </span><span style="color: blue; font-weight: bold">for </span>col <span style="color: blue; font-weight: bold">in </span>slots<span style="font-weight: bold">[</span>gaps<span style="font-weight: bold">:]:
                </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>add_r<span style="font-weight: bold">+</span>i<span style="font-weight: bold">][</span>col<span style="font-weight: bold">] = </span>W
            <span style="color: blue">self</span><span style="font-weight: bold">.</span>rooms<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>Maze<span style="font-weight: bold">(</span>i<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c<span style="font-weight: bold">, (</span>add_r<span style="font-weight: bold">,</span>add_c<span style="font-weight: bold">), </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">))
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rooms<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>Maze<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span>i<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>c<span style="font-weight: bold">, (</span>add_r<span style="font-weight: bold">+</span>i<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">,</span>add_c<span style="font-weight: bold">), </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>root<span style="font-weight: bold">))

        </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">1
      
</span><span style="color: blue; font-weight: bold">def </span>make<span style="font-weight: bold">(</span>room<span style="font-weight: bold">, </span>depth<span style="font-weight: bold">, </span>gaps<span style="font-weight: bold">=</span><span style="color: red">1</span><span style="font-weight: bold">, </span>vert<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">, </span>min_width<span style="font-weight: bold">=</span><span style="color: red">1</span><span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    recursively build a maze
    TODO: randomize number of gaps?
    """
    
    </span><span style="color: green; font-style: italic">## extreme base case
    </span><span style="color: blue; font-weight: bold">if </span>room<span style="font-weight: bold">.</span>r <span style="font-weight: bold">&lt;= </span>min_width <span style="color: blue; font-weight: bold">and </span>room<span style="font-weight: bold">.</span>c <span style="font-weight: bold">&lt;= </span>min_width<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return    
    
    </span><span style="color: green; font-style: italic">## decide between vertical and horizontal wall
    </span><span style="color: blue; font-weight: bold">if </span>vert<span style="font-weight: bold">: </span>num <span style="font-weight: bold">= </span>room<span style="font-weight: bold">.</span>c
    <span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">: </span>num <span style="font-weight: bold">= </span>room<span style="font-weight: bold">.</span>r    
    <span style="color: blue; font-weight: bold">if </span>num <span style="font-weight: bold">&lt; </span>min_width <span style="font-weight: bold">+ </span><span style="color: red">2</span><span style="font-weight: bold">:
        </span>vert <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">not </span>vert
        <span style="color: blue; font-weight: bold">if </span>vert<span style="font-weight: bold">: </span>num <span style="font-weight: bold">= </span>room<span style="font-weight: bold">.</span>c
        <span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">: </span>num <span style="font-weight: bold">= </span>room<span style="font-weight: bold">.</span>r
    
    <span style="color: green; font-style: italic">## add a wall to the current room
    </span><span style="color: blue; font-weight: bold">if </span>depth<span style="font-weight: bold">==</span><span style="color: red">0</span><span style="font-weight: bold">: </span>wall_slots <span style="font-weight: bold">= [</span>num<span style="font-weight: bold">-</span><span style="color: red">2</span><span style="font-weight: bold">]  </span><span style="color: green; font-style: italic">## fix the first wall
    </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">: </span>wall_slots <span style="font-weight: bold">= </span>range<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">, </span>num<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>len<span style="font-weight: bold">(</span>wall_slots<span style="font-weight: bold">) == </span><span style="color: red">0</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return
    </span>choice <span style="font-weight: bold">= </span>random<span style="font-weight: bold">.</span>choice<span style="font-weight: bold">(</span>wall_slots<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if not </span>room<span style="font-weight: bold">.</span>add_wall<span style="font-weight: bold">(</span>choice<span style="font-weight: bold">, </span>gaps<span style="font-weight: bold">, </span>vert<span style="font-weight: bold">): </span><span style="color: blue; font-weight: bold">return

    </span><span style="color: green; font-style: italic">## recursively add walls
    </span><span style="color: blue; font-weight: bold">for </span>sub_room <span style="color: blue; font-weight: bold">in </span>room<span style="font-weight: bold">.</span>rooms<span style="font-weight: bold">:
        </span>make<span style="font-weight: bold">(</span>sub_room<span style="font-weight: bold">, </span>depth<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">, </span>max<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">,</span>gaps<span style="font-weight: bold">/</span><span style="color: red">2</span><span style="font-weight: bold">), </span><span style="color: blue; font-weight: bold">not </span>vert<span style="font-weight: bold">, </span>min_width<span style="font-weight: bold">)

</span><span style="color: blue; font-weight: bold">def </span>copy_grid<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">):
    </span>new_grid <span style="font-weight: bold">= []
    </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>len<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">)):
        </span>new_grid<span style="font-weight: bold">.</span>append<span style="font-weight: bold">([])
        </span><span style="color: blue; font-weight: bold">for </span>col <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>len<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">])):
            </span>new_grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">].</span>append<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">])
    </span><span style="color: blue; font-weight: bold">return </span>new_grid
  
<span style="color: blue; font-weight: bold">def </span>add_pacman_stuff<span style="font-weight: bold">(</span>maze<span style="font-weight: bold">, </span>max_food<span style="font-weight: bold">=</span><span style="color: red">60</span><span style="font-weight: bold">, </span>max_capsules<span style="font-weight: bold">=</span><span style="color: red">4</span><span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    add pacmen starting position
    add food at dead ends plus some extra
    """

    </span><span style="color: green; font-style: italic">## parameters
    </span>max_depth <span style="font-weight: bold">= </span><span style="color: red">2
    
    </span><span style="color: green; font-style: italic">## add food at dead ends
    </span>depth <span style="font-weight: bold">= </span><span style="color: red">0
    </span>total_food <span style="font-weight: bold">= </span><span style="color: red">0
    </span><span style="color: blue; font-weight: bold">while True</span><span style="font-weight: bold">:
        </span>new_grid <span style="font-weight: bold">= </span>copy_grid<span style="font-weight: bold">(</span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">)
        </span>depth <span style="font-weight: bold">+= </span><span style="color: red">1
        </span>num_added <span style="font-weight: bold">= </span><span style="color: red">0
        </span><span style="color: blue; font-weight: bold">for </span>row <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">, </span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">):
            </span><span style="color: blue; font-weight: bold">for </span>col <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">, (</span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">/</span><span style="color: red">2</span><span style="font-weight: bold">)-</span><span style="color: red">1</span><span style="font-weight: bold">):
                </span><span style="color: blue; font-weight: bold">if </span><span style="font-weight: bold">(</span>row <span style="font-weight: bold">&gt; </span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span><span style="color: red">6</span><span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span><span style="font-weight: bold">(</span>col <span style="font-weight: bold">&lt; </span><span style="color: red">6</span><span style="font-weight: bold">): </span><span style="color: blue; font-weight: bold">continue
                if </span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">] != </span>E<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">continue
                </span>neighbors <span style="font-weight: bold">= (</span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">][</span>col<span style="font-weight: bold">]==</span>E<span style="font-weight: bold">) + (</span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">]==</span>E<span style="font-weight: bold">) + (</span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">][</span>col<span style="font-weight: bold">]==</span>E<span style="font-weight: bold">) + (</span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">]==</span>E<span style="font-weight: bold">)
                </span><span style="color: blue; font-weight: bold">if </span>neighbors <span style="font-weight: bold">== </span><span style="color: red">1</span><span style="font-weight: bold">: 
                    </span>new_grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">] = </span>F
                    new_grid<span style="font-weight: bold">[</span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span>row<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">][</span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">-(</span>col<span style="font-weight: bold">)-</span><span style="color: red">1</span><span style="font-weight: bold">] = </span>F
                    num_added <span style="font-weight: bold">+= </span><span style="color: red">2
                    </span>total_food <span style="font-weight: bold">+= </span><span style="color: red">2
        </span>maze<span style="font-weight: bold">.</span>grid <span style="font-weight: bold">= </span>new_grid
        <span style="color: blue; font-weight: bold">if </span>num_added <span style="font-weight: bold">== </span><span style="color: red">0</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">break
        if </span>depth <span style="font-weight: bold">&gt;= </span>max_depth<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">break

    </span><span style="color: green; font-style: italic">## starting pacmen positions
    </span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span><span style="color: red">2</span><span style="font-weight: bold">][</span><span style="color: red">1</span><span style="font-weight: bold">] = </span><span style="color: red">'3'
    </span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span><span style="color: red">3</span><span style="font-weight: bold">][</span><span style="color: red">1</span><span style="font-weight: bold">] = </span><span style="color: red">'1'
    </span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span><span style="color: red">1</span><span style="font-weight: bold">][</span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">-</span><span style="color: red">2</span><span style="font-weight: bold">] = </span><span style="color: red">'4'
    </span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span><span style="color: red">2</span><span style="font-weight: bold">][</span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">-</span><span style="color: red">2</span><span style="font-weight: bold">] = </span><span style="color: red">'2'

    </span><span style="color: green; font-style: italic">## add capsules
    </span>total_capsules <span style="font-weight: bold">= </span><span style="color: red">0
    </span><span style="color: blue; font-weight: bold">while </span>total_capsules <span style="font-weight: bold">&lt; </span>max_capsules<span style="font-weight: bold">:
        </span>row <span style="font-weight: bold">= </span>random<span style="font-weight: bold">.</span>randint<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">, </span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">)
        </span>col <span style="font-weight: bold">= </span>random<span style="font-weight: bold">.</span>randint<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">, (</span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">/</span><span style="color: red">2</span><span style="font-weight: bold">)-</span><span style="color: red">2</span><span style="font-weight: bold">)
        </span><span style="color: blue; font-weight: bold">if </span><span style="font-weight: bold">(</span>row <span style="font-weight: bold">&gt; </span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span><span style="color: red">6</span><span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span><span style="font-weight: bold">(</span>col <span style="font-weight: bold">&lt; </span><span style="color: red">6</span><span style="font-weight: bold">): </span><span style="color: blue; font-weight: bold">continue
        if</span><span style="font-weight: bold">(</span>abs<span style="font-weight: bold">(</span>col <span style="font-weight: bold">- </span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">/</span><span style="color: red">2</span><span style="font-weight: bold">) &lt; </span><span style="color: red">3</span><span style="font-weight: bold">): </span><span style="color: blue; font-weight: bold">continue
        if </span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">] == </span>E<span style="font-weight: bold">:
            </span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">] = </span>C
            maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span>row<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">][</span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">-(</span>col<span style="font-weight: bold">)-</span><span style="color: red">1</span><span style="font-weight: bold">] = </span>C
            total_capsules <span style="font-weight: bold">+= </span><span style="color: red">2

    </span><span style="color: green; font-style: italic">## extra random food
    </span><span style="color: blue; font-weight: bold">while </span>total_food <span style="font-weight: bold">&lt; </span>max_food<span style="font-weight: bold">:
        </span>row <span style="font-weight: bold">= </span>random<span style="font-weight: bold">.</span>randint<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">, </span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">)
        </span>col <span style="font-weight: bold">= </span>random<span style="font-weight: bold">.</span>randint<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">, (</span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">/</span><span style="color: red">2</span><span style="font-weight: bold">)-</span><span style="color: red">1</span><span style="font-weight: bold">)
        </span><span style="color: blue; font-weight: bold">if </span><span style="font-weight: bold">(</span>row <span style="font-weight: bold">&gt; </span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span><span style="color: red">6</span><span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span><span style="font-weight: bold">(</span>col <span style="font-weight: bold">&lt; </span><span style="color: red">6</span><span style="font-weight: bold">): </span><span style="color: blue; font-weight: bold">continue
        if</span><span style="font-weight: bold">(</span>abs<span style="font-weight: bold">(</span>col <span style="font-weight: bold">- </span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">/</span><span style="color: red">2</span><span style="font-weight: bold">) &lt; </span><span style="color: red">3</span><span style="font-weight: bold">): </span><span style="color: blue; font-weight: bold">continue
        if </span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">] == </span>E<span style="font-weight: bold">:
            </span>maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>row<span style="font-weight: bold">][</span>col<span style="font-weight: bold">] = </span>F
            maze<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">-</span>row<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">][</span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">-(</span>col<span style="font-weight: bold">)-</span><span style="color: red">1</span><span style="font-weight: bold">] = </span>F
            total_food <span style="font-weight: bold">+= </span><span style="color: red">2
  
</span>MAX_DIFFERENT_MAZES <span style="font-weight: bold">= </span><span style="color: red">10000

</span><span style="color: blue; font-weight: bold">def </span>generateMaze<span style="font-weight: bold">():
    </span><span style="color: blue; font-weight: bold">import </span>random<span style="font-weight: bold">, </span>sys
    random<span style="font-weight: bold">.</span>seed<span style="font-weight: bold">(</span>random<span style="font-weight: bold">.</span>randint<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">,</span>MAX_DIFFERENT_MAZES<span style="font-weight: bold">))
    </span>maze <span style="font-weight: bold">= </span>Maze<span style="font-weight: bold">(</span><span style="color: red">16</span><span style="font-weight: bold">,</span><span style="color: red">16</span><span style="font-weight: bold">)
    </span>make<span style="font-weight: bold">(</span>maze<span style="font-weight: bold">, </span>depth<span style="font-weight: bold">=</span><span style="color: red">0</span><span style="font-weight: bold">, </span>gaps<span style="font-weight: bold">=</span><span style="color: red">6</span><span style="font-weight: bold">, </span>vert<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">, </span>min_width<span style="font-weight: bold">=</span><span style="color: red">1</span><span style="font-weight: bold">)
    </span>maze<span style="font-weight: bold">.</span>to_map<span style="font-weight: bold">()
    </span>add_pacman_stuff<span style="font-weight: bold">(</span>maze<span style="font-weight: bold">, </span><span style="color: red">2</span><span style="font-weight: bold">*(</span>maze<span style="font-weight: bold">.</span>r<span style="font-weight: bold">*</span>maze<span style="font-weight: bold">.</span>c<span style="font-weight: bold">/</span><span style="color: red">20</span><span style="font-weight: bold">))
    </span><span style="color: blue; font-weight: bold">return </span>str<span style="font-weight: bold">(</span>maze<span style="font-weight: bold">)

</span><span style="color: blue; font-weight: bold">if </span>__name__ <span style="font-weight: bold">== </span><span style="color: red">'__main__'</span><span style="font-weight: bold">:
    </span><span style="color: blue; font-weight: bold">print </span>generateMaze<span style="font-weight: bold">()
</span>
  </pre>
  </body>
  </html>
  